package nonogram;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class NonogramSolver {

	private long runtime = -1;
	private int numRows = 0;
	private int numColumns = 0;
	private boolean solved = false;

	private List<Line> rows = new ArrayList<>();
	private List<Line> columns = new ArrayList<>();

	private Queue<Line> lineSolvingPriority;

	public NonogramSolver(String rowString, String colString) {
		System.out.println(rowString);
		System.out.println(colString);
		loadPuzzle(rowString, colString);
	}

	/**
	 * Sets up the puzzle to be solved.
	 * 
	 * @param rowString
	 *            String of the row groups.
	 * @param colString
	 *            String of the column groups.
	 */
	private void loadPuzzle(String rowString, String colString) {
		String[] rowGroups = rowString.split(",");
		String[] columnGroups = colString.split(",");

		numRows = rowGroups.length;
		numColumns = columnGroups.length;

		// Of this capacity so that every line can be added without error.
		Comparator<Line> comparator = new LineSolvingComparator();
		lineSolvingPriority = new PriorityQueue<>(numRows + numColumns,
				comparator);

		// Create lines for rows .
		for (int i = 0; i < numRows; i++) {
			rows.add(new Line("Row" + i, LineType.ROW, numColumns));
		}

		// Create lines for columns.
		for (int i = 0; i < numColumns; i++) {
			columns.add(new Line("Column" + i, LineType.COLUMN, numRows));
		}

		// Initialize rows and columns with UNKNOWN cells
		// Done this way to Cell in row lines and column lines are the same.
		// So CellType can be changed in one and the other will also be updated.
		for (int i = 0; i < numRows; i++) {
			for (int j = 0; j < numColumns; j++) {
				Cell cell = new Cell();

				rows.get(i).addCell(cell);
				columns.get(j).addCell(cell);
			}
		}

		//
		setupGroups(numRows, rowGroups, rows, numColumns);
		setupGroups(numColumns, columnGroups, columns, numRows);

		System.out.println("Done loading puzzle.");
	}

	/**
	 * Sets up the Group values for each line.
	 * 
	 * @param size
	 *            Number of rows/columns
	 * @param groups
	 *            Array of groups from files
	 * @param lineList
	 *            rows or columns list to add groups to
	 */
	private void setupGroups(int size, String[] groups, List<Line> lineList, int opposingSize) {
		for (int i = 0; i < size; i++) {
			Line line = lineList.get(i);

			String[] groupStrings = groups[i].split("/");



			for (String str : groupStrings) {
				Group group = new Group(Integer.parseInt(str.trim()));
				line.addGroup(group);
			}


		}
	}

	/**
	 * Solves the puzzles, while timing how long it takes.
	 */
	public void solve() {
		long start = System.nanoTime();
		localSolve();
		long end = System.nanoTime();

		runtime = end - start;
	}

	public long getRuntime() {
		return runtime;
	}

	public double getSeconds() {
		return (runtime / 1000000000.0d);
	}

	public void getSolution() {
		// TODO
	}

	public void prettyPrint() {
		System.out.println(this.toString());
	}

	@Override
	public String toString() {
		String border = "";
		for (int i = 0; i < numColumns; i++) {
			border += "--";
		}
		border += "-";

		String str = border + "\n";

		for (Line row : rows) {
			str += row.toString();
			str += "\n" + border + "\n";
		}

		return str;
	}

	public void htmlPrint() {
		System.out.println(this.toHtml());
	}

	public String toHtml() {
		String str = "";

		str += "<html>\n";
		str += "\t<body>\n";
		str += "\t\t<table border='1' cellpadding='10'>\n";

		for (Line row : rows) {
			str += row.toHtml("\t\t\t");
		}

		str += "\t\t</table>\n";
		str += "\t</body>\n";
		str += "</html>\n";

		return str;
	}

	/**
	 * Try to solve each line first. Then while not solved, solve the next line
	 * or guess if needed. Only needs to update the 'solved' variable when no
	 * more line solving can be done.
	 */
	private void localSolve() {
		initialSolveAndPrioritySetup();
		updatedSolved();

		while (!isSolved()) {
			String html = this.toHtml();
//			System.out.println(html);
			Line line = lineSolvingPriority.poll();
			
			if (line != null) {
//				System.out.println("Line: " + line.getId());
				lineSolve(line);
			}
			else {
				updatedSolved();

				if (!isSolved()) {
					// Still not solved after updating.

					guess();

					return; // For now, since guessing isn't there.
				}
			}
		}

	}

	/**
	 * Solves each line as much as possible without any care for other changes
	 * being made. While each line is solved, it adds that line to the priority
	 * queue.
	 */
	private void initialSolveAndPrioritySetup() {
		for (Line row : rows) {
			initialSolveAndPriorityForLine(row, columns);
		}

		for (Line column : columns) {
			initialSolveAndPriorityForLine(column, rows);
		}
	}

	private void initialSolveAndPriorityForLine(Line line,
			List<Line> linesToUpdate) {
		List<Integer> changedIndices = line.quickLineSolve();

		for (int idx : changedIndices) {
			safeAddToPriorityQueue(linesToUpdate.get(idx));
		}

		// If solved, try to remove this line in case it is in the priority
		// queue.
		if (line.isFilledCompletely()) {
			lineSolvingPriority.remove(line);
		}
	}

	// TODO: Decide if useful.
	private Line getPerpendicularLine(LineType type, int lineNum) {
		if (type == LineType.ROW) {
			return columns.get(lineNum);
		}
		else {
			return rows.get(lineNum);
		}
	}

	/**
	 * Update whether or not the puzzle has been solved.
	 */
	private void updatedSolved() {
		for (Line row : rows) {
			if (!row.isSolved()) {
				return;
			}
		}

		solved = true;
	}

	public boolean isSolved() {
		return solved;
	}

	/**
	 * Line solves the line selected from the priority queue.
	 */
	private void lineSolve(Line line) {
		List<Integer> indicesToUpdate = line.lineSolve();
		List<Line> linesToUpdate;

		// If row, update columns; if column, update rows.
		if (line.getType() == LineType.ROW) {
			linesToUpdate = columns;
		}
		else {
			linesToUpdate = rows;
		}

		for (int index : indicesToUpdate) {
			safeAddToPriorityQueue(linesToUpdate.get(index));
		}
		
		// Add own line back to queue if cells were changed.
		// Useful in scenario where cells are crossed out, then filled.
		// But then more could be crossed out, and subsequently more filled.
		if (!indicesToUpdate.isEmpty()) {
			safeAddToPriorityQueue(line);
		}
	}

	/**
	 * 
	 * @param line
	 *            The line to be added to the priority queue.
	 */
	private void safeAddToPriorityQueue(Line line) {

		// Remove line if already in priority queue.
		lineSolvingPriority.remove(line);

		// Add line again if not already solved.
		if (!line.isFilledCompletely()) {
			lineSolvingPriority.offer(line);
		}

	}

	private void guess() {
		// TODO
	}

}
